package 动态规划模型总结;

public class 机器人一维k步 {
	/**
	 * 
	 * @param N 1 ~ N
	 * @param M 当前的位置
	 * @param p 目标位置
	 * @param k 只能 且 必须 走 k steps
	 * @return
	 */
	public static int solution(int N,int M,int p,int k) {
		// 在处理 边界 时候的 一些 小小的技巧 。
		if(M < 1 || M > N )
			return 0;
		if(k == 0)
			return M == p ? 1 : 0;
//		int ans = 0;
//		if(k == 1)
		// 左走
		int ans = solution(N,M - 1,p,k - 1);
		// 右走 
		ans +=solution(N,M + 1,p, k - 1);
		// or return solution(M - 1,k - 1 ) + solution(M + 1,k  -1);
		return ans;
	}
	
	
	public static int dp(int N,int M,int p,int k) {
		int dp[][] = new int [N + 2][k + 1];
		
		for(int step = 0;step <= k;step ++) {
			for(int cur = 1;cur < M ;cur ++) { 
				if(step == 0) {
					dp[cur][step] = cur == p ? 1 : 0;
					continue;
				}
				dp[cur][step] = dp[cur - 1][step - 1] + dp[cur + 1][step - 1];
			}
			
			for(int cur = M;cur <= N ;cur ++) {
				if(step == 0) {
					dp[cur][step] = cur == p ? 1 : 0;
					continue;
				}
				dp[cur][step] = dp[cur - 1][step - 1] + dp[cur + 1][step - 1];
			}
			
		}
		return dp[M][k];
	}
	
	// 优化  写的形式 
	public static int dpFinal(int N,int M,int p,int k) {
		int dp [][] = new int[N + 2][k + 1];
		// basecase
		dp[p][0] = 1;;
		for(int step = 1;step <= k;step ++) {			
			for(int cur = 1;cur <= N;cur++)
				dp[cur][step] = dp[cur + 1][step - 1] + dp[cur - 1][step - 1];
		}
		return dp[M][k];
	}
	
	
	
	
	public static void main(String []args) {
//		System.out.println(solution(5,2,4,6));
//		System.out.println(dp(5,2,4,6));
//		System.out.println(dpFinal(5,2,4,6));
		System.out.println(solution(6,2,4,8));
		System.out.println(dp(6,2,4,8));
		System.out.println(dpFinal(6,2,4,8));
		
	}
}
